package com.markus.code.排序.base1;

/**
 * Author:markusZhang
 * Date:Create in 2020/9/5 20:52
 * todo:
 */
public class QuickSort {
    public static void quickSort(int []arr,int L,int R){
        if (L <= R){
            swap(arr,L+(int)Math.random()*(R-L+1),R);
            int[] partition = partition(arr, L, R);
            quickSort(arr,L,partition[0]-1);
            quickSort(arr,partition[1]+1,R);
        }
    }
    private static int[] partition(int []arr,int L,int R){
        int less = L-1;
        int more = R;
        while(L < more){
            if (arr[L] < arr[R]){
                //进行这步操作，是表示，基准值比左边值大，那么左边值入左边区域，左边区域往右扩
                swap(arr,L++,++less);
            }else if (arr[L] > arr[R]){
                //进行这步操作，是表示，基准值比左边值小，那么交换该值与左边值，右边区域往左扩
                swap(arr,L,--more);
            }else{
                //中间值，与该值相等，L指针移动，进行下一个值的比较
                L++;
            }
        }
        swap(arr,more,R);
        return new int[]{less+1,more};
    }
    private static void swap(int []arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int []arr = {1,3,5,4,3,6};
        quickSort(arr,0,arr.length-1);
        for (int i : arr) {
            System.out.print(i+" ");
        }
    }

}
